/* 测试内容：每次 左旋/右旋 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NAMESIZE 32

struct score_st
{
	int id;
	char name[NAMESIZE];
	int math;
	int chinese;
};

static void print_s(struct score_st *tmp)
{
	if (tmp == NULL)
		printf("not find data.\n");
	else
		printf("%d %s %d %d\n",tmp->id,tmp->name,tmp->math,tmp->chinese);

	return ;
}


struct node_st
{
	struct score_st data;
	struct node_st *l,*r;

};

struct node_st *tree = NULL;


int insert(struct node_st **root,struct score_st *data)
{
	struct node_st *node;
	if((*root) == NULL)/*走一个结点都没有/ 到叶子结点*/
	{
		node = malloc(sizeof(*node));
		if (node == NULL)
			return -1;

		node->data = *data;
		node->l = NULL;
		node->r = NULL;

		(*root) = node;
		return 0;
	}
	

	if(data->id <= (*root)->data.id)/*左孩子*/
		return insert(&(*root)->l,data);
	return insert(&(*root)->r,data);/*右孩子*/


}
struct score_st *find(struct node_st *root,int id)
{
	if (root == NULL)/*叶子结点为空 没找到*/
		return NULL;

	if(id == root->data.id)
		return &root->data;

	if(id <= root->data.id)
		return find(root->l,id);
	else
		return find(root->r,id);

}

static void draw_(struct node_st *root,int level)
{
	int i = 0;
	if (root == NULL)
		return ;

	draw_(root->r,level+1);
	for (i = 0;i< level;i++)
		printf("	");
	print_s(&root->data);

	draw_(root->l,level+1);
}

void draw(struct node_st *root)
{
	draw_(root,0);
	printf("\n");
	getchar();
}



static struct node_st *find_min(struct node_st *root)
{
	if (root->l == NULL)
		return root;
	return find_min(root->l);
}

static struct node_st *find_max(struct node_st *root)
{
	if (root->r == NULL)
		return root;
	return find_max(root->r);
}


static void turn_left(struct node_st **root)
{
	struct node_st *cur = *root;

	*root = cur ->r;
	cur->r = NULL;

	find_min(*root) ->l = cur;//找根结点的左子树 一直找到空 挂上
	draw((*root));

}

static void turn_right(struct node_st **root)
{
	struct node_st *cur = *root;

	*root = cur ->l;
	cur->l = NULL;

	find_max(*root) ->r = cur;
	draw((*root));

}

static int get_num(struct node_st *root)
{
	if (root == NULL)//叶子结点
		return 0;

	return get_num(root->l) + 1 + get_num(root->r); //计算左子树 + 根结点 + 右子树
}


void balance(struct node_st **root)
{
	if (*root == NULL)//叶子结点
		return ;
	int sub = 0;
	while(1)
	{

		sub = get_num((*root)->l) - get_num((*root)->r);//个数
	
		if (sub >= -1 && sub <= 1)//平衡
			break;
		if (sub < -1)// 右多
			turn_left(root);//左旋
		else
			turn_right(root);

	}//平衡完第一个根结点

	balance(&(*root)->l);//平衡左子树
	balance(&(*root)->r);//平衡右子树
}

int main()
{
	struct score_st tmp;
	int arr[] = {1,2,3,7,6,5,9,8,4};
	int i =0;

	for (i = 0;i< sizeof(arr)/sizeof(*arr);i++)
	{
		tmp.id = arr[i];
		snprintf(tmp.name,NAMESIZE,"stu%d",arr[i]);
		tmp.math = rand()%100;
		tmp.chinese = rand()%100;

		insert(&tree,&tmp);
	}

	draw(tree);
	printf("\n");
	/* 平衡规定：根结点的 左 与 右相差结点个数最多为1 逐一左旋 / 右旋*/
	balance(&tree);
	printf("\n\n");
	draw(tree);


	exit(0);
}


